import 'package:unittest/unittest.dart';
import 'package:logging/logging.dart';

import 'dart:math';

import 'rbtree.dart';

final Logger logger = new Logger("test_rbtree");

/** Logs to the console. */
void logConsole(LogRecord lrec) {
  print("${lrec.sequenceNumber} ${lrec.time} ${lrec.level} ${lrec.loggerName} ${lrec.message}");
}

/** Comparator for strings. */
int compare(String s1, String s2) {
  return s1.compareTo(s2);
}

class Pair<A, B> {
  A a;
  B b;
  Pair(this.a, this.b);
}

class PermutationIterator<T> extends Iterator<List<T>> {
  final List<T> _items;
  final int _nitems;

  List<List<int>> _current = null;
  List<List<int>> _possibilities = null;

  factory PermutationIterator(List<T> items) {
    return new PermutationIterator._internal(items, items.length);
  }

  PermutationIterator._internal(this._items, this._nitems);

  bool _increment() {
    if (_current.isEmpty) return false;

    _current.last.removeLast();
    if (_current.last.isEmpty) {
      _current.removeLast();
      _possibilities.removeLast();
      if (!_increment()) return false;

      final List<int> current = new List();
      current.addAll(_possibilities.last);
      current.remove(_current.last.last);
      _current.add(current);
      _possibilities.add(new List.from(current, growable: false));
    }
    return true;
  }

  bool moveNext() {
    final bool init = (_current == null);
    if (!init) return _increment();

    _current = new List<List<int>>();
    _possibilities = new List<List<int>>();

    final List<int> all = new List();
    for (int i = 0; i < _nitems; ++i) all.add(i);

    for (int i = 0; i < _nitems; ++i) {
      final List<int> current = new List();
      if (i == 0) {
        current.addAll(all);
      } else {
        current.addAll(_possibilities.last);
        current.remove(_current.last.last);
      }
      _current.add(current);
      _possibilities.add(new List.from(current, growable: false));
    }
    return !_current.isEmpty;
  }

  List<T> get current {
    final List<T> current = new List(_nitems);
    for (int i = 0; i < _nitems; ++i) {
      current[i] = _items[_current[i].last];
    }
    return current;
  }
}

class PermutationIterable<T> extends Iterable<List<T>> {
  final List<T> _items;

  PermutationIterable(this._items);

  Iterator<List<T>> get iterator {
    return new PermutationIterator(_items);
  }
}

// -------------------------------------------------------------------------------------------------

void main() {
  Logger.root.onRecord.listen(logConsole);
  // Logger.root.level = Level.ALL;

  final int randomSeed = new DateTime.now().millisecondsSinceEpoch;
  logger.info("Random seed is ${randomSeed}");
  final Random random = new Random(randomSeed);

  final List<int> list = [8, 7, 6, 5, 4, 3, 2, 1];
  for (List<int> list in new PermutationIterable<int>(list)) {
    final tree = new RedBlackTree();
    for (int i in list) {
      logger.fine("insert $i -> $i");
      tree.insert(i, i);
    }
    for (int i in list) {
      expect(tree.get(i), i);
    }
    {
      var i = 1;
      for (Entry entry in tree.entries) {
        expect(entry.key, i);
        expect(entry.value, i);
        i += 1;
      }
    }
    final List permutation = new List.from(list, growable: false);
    for (int i = 0; i < permutation.length; ++i) {
      final int sw = random.nextInt(permutation.length);
      final int tmp = permutation[i];
      permutation[i] = permutation[sw];
      permutation[sw] = tmp;
    }
    for (int i in permutation) {
      logger.fine("remove $i");
      expect(tree.remove(i), i);
    }
  }
}